package com.wen.Part6.GraphAlgorithm.impl;

import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;

import java.util.ArrayList;
import java.util.List;

public class Prim implements GraphAlgorithm {
    private String start;

    public Prim(String start) {
        this.start = start;
    }

    @Override
    public Object solve(Graph g) {
        int size = g.getSize();
        // 标记访问
        int[] visited = new int[size];
        // 记录路径
        int[] path = new int[size];
        // 记录开销
        int[] cost = new int[size];

        // 初始化
        for (int i = 0; i < size; i++) {
            path[i] = i;  // 路径初始化为自己
            cost[i] = 10000;  // 开销初始化为特别大
        }


        int next = g.key2Index(start);
        cost[next] = 0;


        // 外部循环n-1次
        for (int i = 0; i < size - 1; i++) {

            // 找出没访问过的，最小点
            int min = 10000;
            for (int j = 0; j < size; j++) {
                if (cost[j] < min && visited[j] == 0){
                    min = cost[j];
                    next = j;
                }
            }
            // 标记访问
            visited[next] = 1;

            // 松弛原则：这条边的代价更小就记住这条边
            for (Integer v : g.getAccessible(next)) {
                if (visited[v] == 0 && g.getWeight(next,v) < cost[v]){
                    cost[v] = g.getWeight(next,v);
                    path[v] = next;
                }
            }
        }

        for (int j = 0; j < size; j++) {
            System.out.println(String.format("%s  --->  %s", g.index2Key(path[j]), g.index2Key(j)));
        }

        return null;
    }

    public static List<String> getKey(Graph g, int[] index){
        List<String> list = new ArrayList<>();
        for (int i = 0; i < g.getSize(); i++) {
            list.add(g.index2Key(index[i]));
        }
        return list;
    }
}
